package cn.xyfmzmy.collection;

import org.w3c.dom.Node;

/**
 * 自定义HashMap
 */
public class MyHashMap<K,V> {

    // hash表,大小为2的幂,这样方便得到合适的下标
    private Node<K,V>[] table = new Node[16];

    // 元素数量
    private int size = 0;

    // 若key已存在,返回被挤出的value;若不存在,返回null
    public V put(K key,V value){
        int index = indexOf(key);
        Node<K, V> head = table[index];
        if(head == null){
            table[index] = new Node<>(key,value);
            size++;
            resizeIfNecessary();
            return null;
        }
        while(true){
            if(head.key.equals(key)){
                V oldValue = head.value;
                head.value = value;
                return oldValue;
            }
            if(head.next == null){
                head.next = new Node<>(key,value);
                size++;
                resizeIfNecessary();
                return null;
            }
            head = head.next;
        }
    }

    public V get(K key){
        int index = indexOf(key);
        Node<K, V> head = table[index];
        while(head != null){
            if(head.key.equals(key)){
                return head.value;
            }
            head = head.next;
        }
        return null;
    }

    public V remove(K key){
        int index = indexOf(key);
        Node<K, V> head = table[index];
        if(head == null){
            return null;
        }
        if(head.key.equals(key)){
            table[index] = head.next;
            size--;
            return head.value;
        }
        Node<K, V> pre = head;
        Node<K, V> cur = head.next;
        while(cur != null){
            if(cur.key.equals(key)){
                pre.next = cur.next;
                size--;
                return cur.value;
            }
            pre = cur;
            cur = cur.next;
        }
        return null;
    }

    public int size(){
        return this.size;
    }

    // 当前元素个数达到table尺寸的3/4时(泊松分布)，自动扩容一倍
    private void resizeIfNecessary(){
        if(this.size < table.length * 0.75){
            return;
        }
        Node<K,V>[] newTable = new Node[this.table.length * 2];
        // 拷贝元素，采用头插法
        for (Node<K, V> head : this.table) {
            if(head == null){
                continue;
            }
            Node<K, V> cur = head;
            while(cur != null){
                Node<K, V> next = cur.next;
                int newIndex = cur.key.hashCode() & (newTable.length -1);
                if(newTable[newIndex] == null){
                    cur.next = null;
                    newTable[newIndex] = cur;
                }else{
                    cur.next = newTable[newIndex];
                    newTable[newIndex] = cur;
                }
                cur = next;
            }
        }
        this.table = newTable;
    }

    private int indexOf(K key){
        // table大小为2的幂，2的幂-1后的二进制是全1，它 & 任何数 得到的都是 <=它的数，且能够全覆盖，很适合作为hash表的下标
        return key.hashCode() & (table.length-1);
    }

    class Node<K,V>{
        K key;
        V value;
        Node<K,V> next;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

}
